//: [Previous](@previous)

/*:
 ### leetcode上第75号问题：Sort Colors
 https://leetcode.com/problems/sort-colors/
 ```
 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 注意:
 不能使用代码库中的排序函数来解决这道题。
 示例:
 输入: [2,0,2,1,1,0]
 输出: [0,0,1,1,2,2]
 ```
 */

import Foundation

// 1. 将 0 1 2 分取出 再合成 / 统计 0 1 2 的个数，在合成
// 时间复杂度 O(n)
// 空间复杂度 O(1)
func SortColors() {
    var nums = [2,0,2,1,1,0]
    var redCount = 0
    var whiteCount = 0
    for num in nums {
        if num == 0 {
            redCount += 1
        } else if num == 1 {
            whiteCount += 1
        }
    }
    for index in 0..<nums.count {
        if index < redCount {
            nums[index] = 0
        } else if index < whiteCount+redCount {
            nums[index] = 1
        } else {
            nums[index] = 2
        }
    }
    print("1. \(nums)", terminator: "\n\n")
}
SortColors()

/* 2. 设定指针 rIndex 对应 1 的首位置
              wIndex 进行循环
              bIndex 对应 1 的末尾位置
 wIndex 进行遍历
 当 nums[wIndex] == 0 时 交换wIndex 和 rInde 位置, wIndex++ rIndex++
 当 nums[wIndex] == 1 时 wIndex++
 当 nums[wIndex] == 2 时 交换wIndex 和 bIndex 位置, bIndex--
 
 时间复杂度 O(n)
 空间复杂度 O(1)
 */

func SortColors2() {
    var nums = [2,0,1]
    var rIndex = -1
    var wIndex = 0
    var bIndex = nums.count
    
    while wIndex < bIndex {
        if nums[wIndex] == 0 {
            rIndex += 1
//            if nums[rIndex] != nums[wIndex] {
                nums.swapAt(rIndex, wIndex)
//            }
//            rIndex += 1
            wIndex += 1
        } else if nums[wIndex] == 2 {
            bIndex -= 1
            nums.swapAt(wIndex, bIndex)
        } else {
            wIndex += 1
        }
    }
    print("2. \(nums)", terminator: "\n\n")
}
SortColors2()



//: [Next](@next)
